The invention relates broadly to data packet communication networks capable of transmitting a digitally coded data packet message including an error-check code from a source node to a destination node over a selected transmission link which includes at least one intermediate node operative to intentionally alter a portion of the message to form an altered message which is ultimately routed to the destination node, and more particularly, to a method of re-computing at the intermediate node a new error-check code for the altered message in a predetermined number of computational operations, i.e. computational time, independent of the length of the message, while preserving the integrity of the initially computed error-check code of the message.
In a data packet or frame-relay communication network, data packet messages are digitally encoded at a source node for transmission over a selected link of the network to a destination node thereof. To protect the integrity of the coded message against errors which may result from transmission or internodal activity, an error-check code is generated at the source node for the message using one of the well known error-check encoding algorithm, such as a cyclic-redundancy-check (CRC) algorithm, for example. The resulting CRC code is appended to the coded message at the source node prior to transmission.
In data packet networks, there is generally included one or more relay or intermediate nodes in the selected transmission link connecting the source and destination nodes. The intermediate node is operative to intentionally alter a portion of the message to form an altered message which is ultimately routed to the destination node. For example, a frame-relay intermediate node may remove its own destination address from the transmission header portion of the coded message and insert in place thereof the address of the next node in the transmission link before passing the altered message on. As a result of this alteration, the originally generated CRC code is no longer valid and must be recomputed based on the altered message. In so doing, the ability to detect errors introduced by preceding transmission and internodal activity should be preserved so that the CRC code received at the destination node will serve to ensure correct end-to-end transmission. Accordingly, any algorithm used to recompute a CRC code pattern at the intermediate node must also ensure end-to-end integrity all along the selected transmission link between the source and destination nodes of the network.
A classical approach for recomputing the CRC code at the intermediate node while preserving error detection integrity includes stripping off the originally generated CRC code from the received message and calculating another CRC code based on the actual coded message received, comparing the original and calculated CRC codes for the detection of errors introduced into the message over the preceding transmission link. If no errors are detected, a new CRC code is computed based on the altered message and the altered message along with the new CRC code are retransmitted together to the next node in the transmission link. If an error is detected, the received message may be dropped at the intermediate node or some default action taken. This classical approach is a process-intensive procedure in that it requires two CRC code encoding computational operations by a conventional byte-wise CRC encoder for each byte of the message, i.e. message length dependent.
Data packet messages normally range in length from 200 bytes to a maximum on the order of 8,000 bytes. Accordingly, using a message length dependent procedure for recalculating a CRC code to accommodate an altered message in an intermediate node of a network requires long computational intervals when the message is comprised of thousands of bytes. Computational times of this magnitude for recalculating CRC codes at intermediate nodes in a network will burden the throughput transmission rates and be prohibitive to data packet transmissions of an overall message like a voice message, for example.
It has been observed, that due to the linearity of CRC codes, the recomputation thereof may be simplified by computing a difference CRC code for the difference portion between the unaltered and altered data messages. The resultant difference CRC code may be added (modulo 2) to the original CRC code to form the new CRC code for the altered message. In this manner, the ability to detect errors in the message from end-to-end utilizing the CRC code thereof is preserved. Examples of such recomputational techniques are referred to in the following references:
(1) D. R. Irvin, "Preserving the Integrity of Cyclic-Redundancy Checks When Protected Text is Intentionally Altered," IBM J. RES. Develop., Vol. 33, pp. 618-626, received by the IEEE Dec. 16, 1988; and accepted for publication Nov. 21, 1989; and PA1 (2) CCITT Study Group XVIII, Question 3-XVIII, Contribution 14, "CRC4--Recommendation Amendments for an Automatic Interworking and Message Channel Capability," February, 1990.
However, the recomputation time of the foregoing described recomputational technique remains message length dependent for the computation of the difference CRC code and thus, may require up to a maximum of 8,000 or so computation operations therefor. Accordingly, this recomputation time for internodal transmission of data packet messages is still believed prohibitive for lengthy data messages.
The present invention provides for a recomputational procedure which overcomes the drawbacks of the foregoing described techniques by recomputing the CRC code in a computational time virtually independent of the message length. This computational procedure provides the highest gain for very long data messages and a small number of altered bytes.